home *** CD-ROM | disk | FTP | other *** search
/ NetNews Offline 2 / NetNews Offline Volume 2.iso / news / comp / lang / c-part1 / 9482 < prev    next >
Encoding:
Internet Message Format  |  1996-08-05  |  1.6 KB
  1. Path: keats.ugrad.cs.ubc.ca!not-for-mail
  2. From: c2a192@ugrad.cs.ubc.ca (Kazimir Kylheku)
  3. Newsgroups: comp.lang.c
  4. Subject: Re: Best Binary Search Tree Balance Algo?
  5. Date: 10 Mar 1996 13:23:29 -0800
  6. Organization: Computer Science, University of B.C., Vancouver, B.C., Canada
  7. Message-ID: <4hvh8hINN5vq@keats.ugrad.cs.ubc.ca>
  8. References: <4hqvc5$p9k@solaria.cc.gatech.edu> <richmond-0903962355070001@aux82.plano.net>
  9. NNTP-Posting-Host: keats.ugrad.cs.ubc.ca
  10.  
  11. In article <richmond-0903962355070001@aux82.plano.net>,
  12. Charles Richmond <richmond@plano.net> wrote:
  13.  >In article <4hqvc5$p9k@solaria.cc.gatech.edu>, bigdave@cc.gatech.edu
  14.  >(David Mitchell) wrote:
  15.  >> I would like to know what the run-time of the best binary search tree 
  16.  >> balance algorithm is.  (e.g. O(n^2), O(n lg n), etc.).
  17.  >> 
  18.  >I believe the AVL balanced tree algorithm is the fastest. It works in
  19.  >big-O of log base 2 of n. The red/black balanced tree algorithm is
  20.  
  21. It works in O(log n) for doing a rebalancing operation when you insert one node
  22. into an already balanced tree. 
  23.  
  24.  >*almost* as good. It works in the same big-O time, but has larger constant
  25.  >terms in the performance equation.
  26.  
  27. I think you got that backwards. AVL is the intuitive, but slow, way to do tree
  28. balancing.  Red-Black is the clever algorithm which gives you the same
  29. asymptotic complexity as AVL, but improves the constants.
  30.  
  31. Red-Black does not achieve perfect order, but it does ensure that the deepest
  32. node is not more than twice as deep as the shallowest node. By enforcing this
  33. constraint, it ensures that lookups are still O(log n) (this is easy to prove),
  34. but the re-balancing is sped up.
  35. -- 
  36.  
  37.